import java.util.ArrayList;
import java.util.List;

/**
 * Created by zhourh on 2018/9/10.
 *
 * 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

 例如：

 输入: 二叉搜索树:
     5
   /   \
 2     13

 输出: 转换为累加树:
     18
    /   \
 20     13

 */
public class ConvertBSTToGreaterTree {

    private int ssum = 0;

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(2);
        root.right = new TreeNode(13);
        Printer.printTreeNode(new ConvertBSTToGreaterTree().convertBST2(root));
    }

    public TreeNode convertBST2(TreeNode root) {
        travelTree(root, ssum);
        return root;
    }


    public void travelTree(TreeNode node, int sum) {
        ssum = sum;
        if (node == null) {
            return;
        }

        // 先处理右子树
        travelTree(node.right, ssum);

        // 处理根节点
        ssum += node.val;
        node.val = ssum;

        // 处理左子树
        travelTree(node.left, ssum);
    }

    public TreeNode convertBST(TreeNode root) {

        if (root == null) {
            return null;
        }

        List<TreeNode> nodeList = new ArrayList<>();
        sortList(root, nodeList);

        for (int i = nodeList.size() - 1; i >= 0; i--) {
            if (i == nodeList.size() - 1) {
                continue;
            }
            nodeList.get(i).val += nodeList.get(i + 1).val;
        }

        return root;
    }

    public void sortList(TreeNode node, List<TreeNode> nodeList) {
        if (node.left != null) {
            sortList(node.left, nodeList);
        }
        nodeList.add(node);
        if (node.right != null) {
            sortList(node.right, nodeList);
        }
    }

}
